﻿//
// KwData v2.0.0
// Copyright © 2009-2012 - Kasey Osborn (Kasewick@gmail.com)
// Ms-PL - Use and redistribute freely
//
// File:    BtreeDictionary.cs
// Purpose: Defines generic API of BtreeDictionary class.
//

using System;
using System.Collections.Generic;
using System.Diagnostics;

[assembly: CLSCompliant (true)]
namespace Kw.Data
{
    /// <summary>Represents a collection of key/value pairs that are sorted on the key.
    /// </summary>
    /// <typeparam name="TKey">The type of the keys in the dictionary.</typeparam>
    /// <typeparam name="TValue">The type of the values in the dictionary.</typeparam>
    /// <remarks>
    /// <para>
    /// Storage space is guaranteed to stay within O(n) for any number of insertions
    /// and deletions, where n is size of collection.
    /// Worst case time is O(log n) for searches, insertions, and deletions, where n is
    /// size of collection.
    /// </para>
    /// <para>
    /// This class is a functional equivalent of the System.Collections.Generic.SortedDictionary
    /// class. However, performance is improved in many areas with this class due to
    /// the clustering of data leading to fewer traversal operations and more hits on
    /// cache memory.  Garbage collection activities should be reduced due to the fewer number
    /// of allocations and the reuse of space.
    /// </para>
    /// <para>
    /// Disclaimer: There are no known bugs in this class, however it has not seen the
    /// testing that SortedDictionary has. Use at your own risk.
    /// </para>
    /// </remarks>
    public partial class BtreeDictionary<TKey, TValue> :
        IDictionary<TKey, TValue>,
        ICollection<KeyValuePair<TKey, TValue>>,
        IEnumerable<KeyValuePair<TKey, TValue>>,
        System.Collections.IDictionary,
        System.Collections.ICollection,
        System.Collections.IEnumerable
        where TKey : IComparable
    {
        internal Branch<TKey> root;
        internal IComparer<TKey> comparer;
        internal int height;
        private BtreeKeys keys;
        private BtreeValues values;
        const int MinimumOrder = 5;
        const int MaximumOrder = 64;

        #region Constructors

        /// <summary>Make a new sorted dictionary consisting of TKey/TValue pairs.</summary>
        public BtreeDictionary ()
            : this (MaximumOrder, null)
        { }


        /// <summary>Make a new sorted dictionary consisting of TKey/TValue pairs.</summary>
        /// </exclude>
        public BtreeDictionary (int newOrder)
            : this (newOrder, null)
        { }


        /// <summary>Create a sorted dictionary consisting of TKey/TValue pairs. Keys
        /// will be sorted using the supplied comparison operator.</summary>
        /// <param name="newComparer">Comparison operator for keys.</param>
        public BtreeDictionary (IComparer<TKey> newComparer)
            : this (MaximumOrder, newComparer)
        { }


        /// <summary>Make a new sorted dictionary consisting of TKey/TValue pairs.</summary>
        /// <param name="newOrder">Maximum number of children of a branch (Keys/node+1).</param>
        /// <param name="newComparer">Comparison operator for keys.</param>
        public BtreeDictionary (int newOrder, IComparer<TKey> newComparer)
        {
            if (newOrder < MinimumOrder)
                throw new ArgumentOutOfRangeException ("newOrder", "Minimum value is " + MinimumOrder);

            if (newComparer == null)
                newComparer = Comparer<TKey>.Default;

            // Create an empty tree consisting of an empty branch and an empty leaf.
            root = new Branch<TKey> (new Leaf<TKey, TValue> (newOrder), newOrder);
            height = 2;

            comparer = newComparer;

            // Allocate the subcollections.
            keys = new BtreeKeys (this);
            values = new BtreeValues (this);
        }


        /// <summary>Create a new sorted dictionary that consists of key/value pairs from the
        /// supplied source.</summary>
        /// <param name="dictionary">The source of the contents of the new dictionary.</param>
        public BtreeDictionary (IDictionary<TKey, TValue> sourceDictionary)
            : this (sourceDictionary, null)
        { }


        /// <summary>Create a new sorted dictionary that consists of key/value pairs from the
        /// supplied source.</summary>
        /// <param name="sourceDictionary">The source of the contents of the new dictionary.</param>
        /// <param name="newComparer"></param>
        public BtreeDictionary (IDictionary<TKey, TValue> sourceDictionary, IComparer<TKey> newComparer)
            : this (newComparer)
        {
            foreach (KeyValuePair<TKey, TValue> pair in sourceDictionary)
                Add (pair.Key, pair.Value);
        }

        #endregion

        #region Methods


        /// <summary>Adds an element with the specified key and value.</summary>
        /// <param name="key">The key of the element to add.</param>
        /// <param name="value">The value of the element to add.  May be null.</param>
        /// <exception cref="ArgumentNullException">When <em>key</em> is <b>null</b>.</exception>
        /// <exception cref="ArgumentException">When supplied <em>key</em>
        /// has already been added.</exception>
        public void Add (TKey key, TValue value)
        {
            if (key == null)
                throw new ArgumentNullException ("key", "Value cannot be null.");

            var path = new TreePath<TKey, TValue> (this, key);
            if (path.IsFound)
                throw new ArgumentException ("An entry with the same key already exists.");

            Insert (path, key, value);
        }


        /// <summary>Remove all key/value pairs from the collection.</summary>
        public void Clear ()
        {
            root = new Branch<TKey> (new Leaf<TKey, TValue> (Order), Order);
            Count = 0;
        }


        /// <summary>Determine if the collection contains the supplied key.</summary>
        /// <param name="pair">Key to find.</param>
        /// <returns><b>true</b> if the collection contains the supplied key;
        /// otherwise <b>false</b>.</returns>
        /// <exception cref="ArgumentNullException">When supplied key is null.</exception>
        public bool ContainsKey (TKey key)
        {
            if (key == null)
                throw new ArgumentNullException ("Value cannot be null.");

            var path = new TreePath<TKey, TValue> (this, key);
            return path.IsFound;
        }


        /// <summary>Determine if the collection contains the supplied value.</summary>
        /// <remarks>This operation performs a sequential search.</remarks>
        /// <param name="value">Value to find.</param>
        /// <returns><b>true</b> if the collection contains the specified value;
        /// otherwise <b>false</b>.</returns>
        public bool ContainsValue (TValue value)
        {
            foreach (KeyValuePair<TKey, TValue> pair in this)
                if (pair.Value.Equals (value))
                    return true;

            return false;
        }


        /// <summary>Copy the collection to the specified array offset.</summary>
        /// <param name="array">Destionation of copy.</param>
        /// <param name="index">Offset to begin copy.</param>
        /// <exception cref="ArgumentNullException">When <em>array</em> is <b>null</b>.</exception>
        /// <exception cref="ArgumentOutOfRangeException">When <em>arrayIndex</em> is less than 0.</exception>
        /// <exception cref="ArgumentException">When not enough space is given for the copy.</exception>
        public void CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException ("array", "Value cannot be null.");

            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException ("arrayIndex", "Index is less than zero.");

            if (arrayIndex + Count > array.Length)
                throw new ArgumentException ("Destination array is not long enough to copy all the items in the collection. Check array index and length.");

            foreach (KeyValuePair<TKey, TValue> pair in this)
            {
                array[arrayIndex] = pair;
                ++arrayIndex;
            }
        }


        /// <summary>Gets an enumerator that iterates thru the collection.</summary>
        /// <returns>An enumerator for the collection.</returns>
        /// <remarks>Implements IEnumerable&lt;KeyValuePair&lt;TKey, TValue&gt;&gt;.</remarks>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
        { return new BtreeEnumerator (this); }


        /// <summary>Remove the key/value pair from the dictionary.</summary>
        /// <param name="key">The key of the element to remove.</param>
        /// <returns><b>true</b> if the element was successfully found and removed;
        /// otherwise <b>false</b>.</returns>
        public bool Remove (TKey key)
        {
            if (key == null)
                throw new ArgumentNullException ("key", "Value cannot be null.");

            TreePath<TKey, TValue> path = new TreePath<TKey, TValue> (this, key);
            if (!path.IsFound)
                return false;

            Delete (path);
            return true;
        }


        /// <summary>Get the value associated with the supplied key.</summary>
        /// <param name="key">Target of search.</param>
        /// <param name="value">If the key is found, its value is placed here; otherwise
        /// it will be loaded with the default value for its type.</param>
        /// <returns><b>true</b> if supplied key is found; otherwise <b>false</b>.</returns>
        /// <exception cref="ArgumentNullException">When <em>key</em> is <b>null</b>.</exception>
        public bool TryGetValue (TKey key, out TValue value)
        {
            if (key == null)
                throw new ArgumentNullException ("Value cannot be null.");

            int index;
            Leaf<TKey, TValue> leaf = Find (key, out index);
            if (leaf != null)
            {
                value = leaf.GetValue (index);
                return true;
            }
            else
            {
                value = default (TValue);
                return false;
            }
        }

        // ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----

        /// <summary>Provides sequential access to the key/value collection.</summary>
        public sealed class BtreeEnumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            // Long form is 10% faster than yield syntax form.
            BtreeDictionary<TKey, TValue> target;
            Leaf<TKey, TValue> currentLeaf;
            int leafIndex;

            public BtreeEnumerator (BtreeDictionary<TKey, TValue> tree)
            {
                target = tree;
                Reset ();
            }

            object System.Collections.IEnumerator.Current
            { get { return (object) Current; } }

            public KeyValuePair<TKey, TValue> Current
            { get { return currentLeaf.GetPair (leafIndex); } }

            public bool MoveNext ()
            {
                if (++leafIndex < currentLeaf.KeyCount)
                    return true;

                leafIndex = 0;
                currentLeaf = currentLeaf.RightLeaf;
                return currentLeaf != null;
            }

            public void Reset ()
            { leafIndex = -1; currentLeaf = target.FirstLeaf; }

            public void Dispose () { GC.SuppressFinalize (this); }
        }

        #endregion

        #region Properties

        /// <summary>Maximum number of children of a branch.</summary>
        internal int Order
        { get { return root.KeyCapacity + 1; } }

        /// <summary>Used to order keys in the sorted dictionary.</summary>
        /// <remarks>To override sorting based on the default comparer, supply an
        /// alternate comparer when constructed.</remarks>
        public IComparer<TKey> Comparer
        { get { return comparer; } }


        /// <summary>Get the number of key/value pairs in the dictionary.</summary>
        public int Count
        { get; private set; }


        /// <summary>Get or set the value associated with the supplied key.</summary>
        /// <param name="key">The key of the association.</param>
        /// <returns>Value associated with the specified key.</returns>
        /// <exception cref="ArgumentNullException">When <em>key</em> is <b>null</b>.</exception>
        /// <exception cref="KeyNotFoundException">When getting a value for a non-existant key.</exception>
        /// <remarks>Setting a value for a non-existant key performs an insert operation.</remarks>
        public TValue this[TKey key]
        {
            get
            {
                if (key == null)
                    throw new ArgumentNullException ("key", "Value cannot be null.");

                int index;
                Leaf<TKey, TValue> leaf = Find (key, out index);
                if (leaf == null)
                    throw new KeyNotFoundException ("The given key was not present in the dictionary.");
                return leaf.GetValue (index);
            }
            set
            {
                if (key == null)
                    throw new ArgumentNullException ("key", "Value cannot be null.");

                var path = new TreePath<TKey, TValue> (this, key);
                if (path.IsFound)
                    path.LeafValue = value;
                else
                    Insert (path, key, value);
            }
        }


        /// <summary>Get the collection of keys in the dictionary.</summary>
        public ICollection<TKey> Keys
        { get { return keys; } }


        /// <summary>Get the collection of values in the dictionary.</summary>
        public ICollection<TValue> Values
        { get { return values; } }

        #endregion

        #region Explicit Methods
        // ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----

        /// <summary>Adds an element with the specified key/value pair.</summary>
        /// <param name="keyValuePair">Contains the key and value of the element to add.</param>
        /// <exception cref="ArgumentException">When supplied <em>key</em>
        /// has already been added.</exception>
        void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
        {
            var path = new TreePath<TKey, TValue> (this, keyValuePair.Key);
            if (path.IsFound)
                throw new ArgumentException ("An entry with the same key already exists.");

            Insert (path, keyValuePair.Key, keyValuePair.Value);
        }


        /// <summary>Determine if the collection contains the supplied key and value.</summary>
        /// <param name="pair">Key/value pair to find.</param>
        /// <returns><b>true</b> if the collection contains the specified pair;
        /// otherwise <b>false</b>.</returns>
        bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> pair)
        {
            var path = new TreePath<TKey, TValue> (this, pair.Key);
            if (!path.IsFound)
                return false;

            Leaf<TKey, TValue> leaf = (Leaf<TKey, TValue>) path.TopNode;
            return (pair.Value.Equals (leaf.GetValue (path.TopNodeIndex)));
        }


        /// <summary>Indicate that this collection may be modified.</summary>
        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
        { get { return false; } }


        /// <summary>Get the collection of keys from this key/value the collection.</summary>
        /// <remarks>The keys given by this collection are sorted according to the
        /// <see cref="Comparer"/> property.</remarks>
        ICollection<TKey> IDictionary<TKey, TValue>.Keys
        { get { return (ICollection<TKey>) keys; } }


        /// <summary>Delete the supplied key and its associated value from the collection.
        /// </summary>
        /// <param name="pair">Contains key and value to find and remove. No operation is taken
        /// unless both key and value match.</param>
        /// <returns><b>true</b> if key/value pair removed; otherwise <b>false</b>.</returns>
        bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> pair)
        {
            var path = new TreePath<TKey, TValue> (this, pair.Key);
            if (path.IsFound)
                if (pair.Value.Equals (path.LeafValue))
                {
                    Delete (path);
                    return true;
                }

            return false;
        }

        /// <summary>Get the collection of values from this key/value collection.</summary>
        /// <remarks>The values given by this collection are sorted in the same
        /// order as their respective keys in the <see cref="Keys"/> property.</remarks>
        ICollection<TValue> IDictionary<TKey, TValue>.Values
        { get { return (ICollection<TValue>) values; } }

        #endregion
    }
}
